"""
file: routing.py
language: python3
author: Zack Butler, Sean Strout
author: Sean Strout
author: Ben K Steele
description: Main program for Message Routing 2 Problem 
"""

from StudentPlayers.TheFightingPenguins.bfs.myStack import *
from  StudentPlayers.TheFightingPenguins.bfs.myQueue import *
     
def searchBFS(source, destination, board):        
    """Performs a BFS search between source and destination nodes using a 
    queue.  It returns the path as a                 square.populateNeighbors()
list of graph nodes (or an empty list
    if no path exists).
    """

    # 'prime' the dispenser with the source 
    dispenser = Queue()
    enqueue(source, dispenser)

    # construct the predecessors data structure
    predecessors = {}
    predecessors[str(source.loc)] = None

    # loop until either the destination is found or the dispenser 
    # is empty (no path)
    while not emptyQueue(dispenser):
        current = front(dispenser)
        dequeue(dispenser)
        if current == destination:
            break
        # loop over all neighbors of current
        for neighbor in current.neighbors:
            # process unvisited neighbors
            if str(neighbor) not in predecessors:
                predecessors[str(neighbor)] = current
                enqueue(board[neighbor[0]][neighbor[1]], dispenser)

    return constructPath(predecessors, source, destination)
        
def constructPath(predecessors, source, destination):
    """Returns the path as a list of nodes from source to destination"""
    
    # construct the path using a stack and traversing from the destination
    # node back to the source node using Node's previous
    stack = Stack()
    CHECKTMP = str(destination.loc) in predecessors
    if str(destination.loc) in predecessors:
        tmp = destination
        while tmp.loc != source.loc:
            push(tmp, stack)
            tmp = predecessors[str(tmp.loc)]
        push(source, stack)
        
    path = []
    while not emptyStack(stack):
        temp1=top(stack)
        path.append([temp1.loc[0],temp1.loc[1]]) 
        pop(stack)   
    return path